1. Field of the Invention
The present invention is related to communications and in particular to the allocation of buffer space in a networking device for temporary storage of data which is transferred between networks or between a host processor and a communications network.
2. Description of the Related Art
Networking devices (NDs) are used in computer networks to perform communications tasks, such as offloading communications related processing from the host processor. The ND is interposed between multiple networks, or the host processor and the network to which it is attached. The ND has processing units and memory, and it executes communication specific tasks.
In a networking device, such as a bridge, a router or a host network adaptor, data packets are received from the attached network and are stored in buffers. Then, they are forwarded to the on-board processing unit (if one is included in the ND), to the host system, or to another network. A special buffer memory is used for the purpose of storing data packets before forwarding them.
Several methods have been used to allocate buffer space for incoming packets, and to release that space after the associated packets are forwarded. In general, the entire buffer memory is partitioned into a number of buffers having a fixed size, in order to simplify the memory management operation. Two buffer memory management methods have been widely used.
The first method employs buffers which have a single size. The number of buffers used to store a packet is limited to a predetermined maximum number. Some systems use a single buffer to store the whole data packet, whereas other systems include multiple buffers to store a packet. If a single buffer is used, its size must be large enough to contain any packet received by the ND. The single buffer allocation scheme is very simple (each packet is assigned to one buffer), but the buffer memory utilization may be extremely inefficient. This is particularly true if the packets vary in size.
On the other hand, to overcome the low memory utilization problem, the buffer memory may be partitioned into small buffers; and every packet is stored in as many buffers as needed to contain the entire packet. This, however, results in a more complex buffer memory management scheme, because all the buffers used for a given packet must be linked together in some fashion, so that they are retrieved when the packet is forwarded as an entity.
The second method employs a plurality of different buffer sizes. The buffer memory is partitioned into multiple sets of buffers, each set having buffers of a given size. Each data packet is stored in a single buffer which is large enough to contain the packet. Different sets include buffers of different sizes. This method may, however introduce additional complexity if the length of the received data packet is not given in its header. In that case, the appropriate buffer pool cannot be selected until the entire packet is received in a temporary storage element and its total size is identified. This can lengthen the time required to store the packet into the buffer.
The buffer memory allocation scheme inside the networking device is an important factor affecting system throughput and utilization. More precisely, the buffer memory inside the ND is managed by a buffer memory management unit (e.g., an on-board general purpose or specialized processor). Every buffer allocation causes management overhead. The allocation of buffer space is a relatively time consuming process for the ND's processor to execute. The allocation process may require a large number of clock cycles per data packet for memory management operations (e.g., management of queues when a packet is received and when it is released after transmission). Furthermore, if multiple buffers are allocated for one received packet, management overhead also becomes larger and the system throughput suffers because of the limitation on the number of buffers that are handled per unit of time by the buffer memory management unit.
In prior systems, to reduce the management overhead, a single buffer for every packet has been used to achieve minimum overhead. However, to accommodate one packet in a single buffer requires that the buffer size be the size of the largest packet which may possibly be received. For example, 4500 byte buffers would be required for a fiber distributed data interface (FDDI) network. In this case, if small packets are more likely to be received or transmitted in a given environment, the actual utilization of the buffer memory becomes very low. This is a problem because the ND is unable to store further packets which it receives, after it runs out of buffers. These further packets are then lost, even though the buffer memory may have large amounts of unused space.
Accordingly, it is desired to allocate buffer space so that a reasonable balance is maintained between the buffer memory utilization and the memory management overhead.